"""
数学课上，老师出了一道题目，
要求在给定的一些数字中找出两个数，使得它们的和为 N，
前提是这些数据中保证有答案，并且只有一个答案。

例如给定 5 个数字：3、4、5、7、10，
从中选择两个数使它们的和为 11，
可以选择 4 和 7，
"""


def func(array, num):
    # 返回数值
    result = []
    templi = []  # 临时存放已经存在的数，并将其跳过
    for i in array:
        if i in templi:
            continue
        if num - i in array and num - i != i:
            templi.append(num - i)
            result.append((i, num - i))
    return result


def func_v2(array, num):
    # 返回下标
    result = []
    templi = []  # 临时存放已经存在的数，并将其跳过
    for i, j in enumerate(array):
        if j in templi:
            continue
        if num - j in array and num - j != j:
            templi.append(num - j)
            result.append((i + 1, array.index(num - j) + 1))
    return result


def twoSum(nums, target):
    res = []  # 存放结果编号数据
    newnums = nums[:]  # 深拷贝，把原数据复制到 newnums 里
    newnums.sort()  # 对新数组排序
    left = 0
    right = len(newnums) - 1  # 定义 left 和 right 指针分别指向新数组的开头和结尾

    while left < right:
        if newnums[left] + newnums[right] == target:
            for i in range(0, len(nums)):  # 在原始数组中寻找第一个元素的原始下标
                if nums[i] == newnums[left]:
                    res.append(i)  # 将下标加入结果集
                    break
                for i in range(len(nums) - 1, -1, -1):  # 在原始数组中寻找第二个元素的原始下标
                    if nums[i] == newnums[right]:
                        res.append(i)  # 将下标加入结果集
                        break
            res.sort()
            break
        elif newnums[left] + newnums[right] < target:
            left = left + 1  # 让 left 指针向右移动一位
        elif newnums[left] + newnums[right] > target:
            right = right - 1  # 让 right 指针向左移动一位
    return res[0] + 1, res[1] + 1  # 返回结果集


def twoSum_v2(nums, target):
    dict = {}
    for i in range(len(nums)):
        m = nums[i]  # 定义 m 为当前待查询的数字
        if target - m in dict:  # 判定 target-m 是否已经在字典中
            return dict[target - m] + 1, i + 1  # 如果已经存在，则返回这两个数的下标
        dict[m] = i  # 如果不存在则记录键值对


if __name__ == '__main__':
    num_li = [3, 4, 5, 7, 10]
    target = 11

    print(func(num_li, target))
    print(func_v2(num_li, target))
    print(twoSum(num_li, target))
    print(twoSum_v2(num_li, target))
